package jdk.utils;

import org.junit.Test;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;


/**
 * HashMap 学习
 *  HashMap 数据结构：  数组（）+链表（）+红黑树
 *
 *      1.HashMap 的最大容量是 1 << 30  ：  2的30次方（1073741824  10亿）
 *        Integer 范围：-31次方  ~2的31次方-1    范围：（-2147483648  ~  2147483647），也就是HashMap的最大容量是Integer最大数的一半。
 *        而HashMap的加载因子是 loadFactories=0.75，既当内部数组被用到四分之三的时候，便不能再加入数据了，理论map.size()最大值是2的30次方*0.75=1610612736（这里的考虑是错误的，当扩容最大size>最大容量时候，就直接扩容到Integer.Max）
 *
 *      2. HashMap 的⻓度为什么保证是2的幂次⽅(取模和扩容时做优化，同时为了减少冲突)，怎么保证的？
 *
 *         取模运算在包括JAVA在内的大多数语言中的效率都十分低下，而当除数为2的N次方时，取模运算将退化为最简单的位运算，其效率明显提升（按照Bruce Eckel给出的数据，大约可以提升5～8倍） 。看
 *
 *         一般取余： hash%length(效率低下)    ==   hash&(length-1) ，   前提是 length 是2的n 次⽅，采⽤⼆进制位操作 &，相对于%能够提⾼运算效率
 *
 *         因为当传入一个数的时候，HashMap有个方法是将数该数计算成大于概数最近的2的N次方。如下：
 *         2的8次方=256，2的7次方128，那么当我传入的size是128~256之间的话，那么HashMap计算出来的size全市256，如果传入的值是64~128 ，那么计算的值全部是128
 *
 *
 *      3.HashMap的长度为什么要保证是2的幂次方
 *         因为HashMap存储数组的下标是通过key的hash值计算出来的，但是hash值有可能大于HashMap的长度N，所以计算下标就用了（N-1）%hash,这个值就肯定小于数组容量了。
 *      这也就解释了为什么N必须是2的幂次方：因为N是2的次幂，因此（N-1）类似于一个掩码，通过与操作，高位的hash值全部为0，保证低位才有效，保证获得的值都是小于N，而且在下个
 *      重写扩容计算resize()方法时候，重新计算每个Node的数组下标就会变得很简单。
 *         （N-1）&hash的缺点是由于只取到低位，所以hash碰撞就会很严重，这时候就得使用扰动函数。如下，HashMap计算key的hash()算法：
 *
 *          static final int hash(Object key) {
 *               int h;
 *               return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 *           }
 *
 *           又在高位进行了或计算
 *
 *
 *      4.HashMap的数据结构
 *      HashMap是数组+链表（Node）+红黑树
 *
 *      Node的数据结构：
 *
 *          static class Node<K,V> implements Map.Entry<K,V> {
 *                final int hash;//该节点的hash值
 *                final K key; //key
 *                V value;    //value
 *                Node<K,V> next;  //下一个节点
 *           }
 *      数组的数据结构：
 *
 *           transient Node<K,V>[] table; resize()方法里面创建新的数组 ----->  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
 *
 *
 *      红黑树：
 *           static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
 *                TreeNode<K,V> parent;  // 红黑树的父节点
 *                TreeNode<K,V> left;    //红黑树的左节点
 *                TreeNode<K,V> right;
 *                TreeNode<K,V> prev;    // 需要解除下一个删除链接  （不懂）
 *                boolean red;  //是否为红节点
 *
 *          }
 *
 *
 *      5.一些初始化的数量：
 *       DEFAULT_LOAD_FACTOR = 0.75f：默认的加载因子是0.75，当存储的元素个数size是数组大小的0,75倍时，出发扩容条件。（HashMap扩容是在之前的容量基础上扩容两倍），为什么设计成0.75F，
 *                                    是对空间和时间效率的一个平衡选择，加载因子太小，就不断出发扩容机制，加载因子太大，即使是最好的hash算法，也避免不了hash碰撞。当然，加载因子可以>1,此时
 *                                    新插入的元素，会不断的有hash碰撞。
 *       DEFAULT_INITIAL_CAPACITY = 1 << 4： 默认初始化容量是16.
 *       MAXIMUM_CAPACITY = 1 << 30：最大容量 2的30次方（1073741824  10亿）
 *       TREEIFY_THRESHOLD = 8：链表转换成树的最大长度是8，当链表大于8的长度时候，就将链表转换成红黑树
 *       UNTREEIFY_THRESHOLD = 6:由红黑树转换成链表的阈值，当小于6时候，就变成链表。
 *       MIN_TREEIFY_CAPACITY=64：最小树化形阈值，既当哈希表中的容量N > 该值时，才允许树形化链表 。原因：若桶内元素太多时，则直接扩容，而不是树形化
 *
 *       问题：为什么扩容那是原来的基础上扩容2倍
 *
 *            扩容后创建一个新的数组，然后将旧的数组数据要进行复制，2倍后的数组插入的元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置，省去了重新计算hash值的时间
 *
 *       6.HashMap put（）方法的逻辑
 *
 *       ①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；（扩容）
 *       ②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；（根据Hash计算元素位置）
 *       ③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
 *       ④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
 *       ⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；（链表转红黑树）
 *       ⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
 *
 *       关键点：扩容原理，hash计算原理，链表转红黑树原理。
 *
 *
 *
 *       7.HashMap扩容机制（使用一个新的数组代替已有的容量小的数组，）  扩容条件：size> loadfactories*n
 *
 *       void resize(int newCapacity) {   //传入新的容量
 *          Entry[] oldTable = table;    //引用扩容前的Entry数组
 *         int oldCapacity = oldTable.length;
 *         if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
 *             threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
 *             return;
 *         }
 *
 *        Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
 *        transfer(newTable);                         //！！将数据转移到新的Entry数组里
 *        table = newTable;                           //HashMap的table属性引用新的Entry数组
 *        threshold = (int)(newCapacity * loadFactor);//修改阈值
 *   }
 *
 *
 *
 *      注意：扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
 *
 *    8.多线程情况下，HashMap put元素会发生什么？
 *
 *       丢失元素
 *
 *       1.当多线程同时put值的时候，若发生hash碰撞，可能多个元素都落在链表的头部，（头插法）从而造成元素覆盖（hashcode相同而eques值不同的元素）
 *       列如：线程A put一个元素a ，线程B put一个元素b，a,b 发生hansh碰撞，本应该在map是链表的形式存在，但是可能线程A和线程B同时put到链表的第一个位置，从而后来者覆盖前者元素造成元素丢失。
 *
 *       2.put 造成链表形成闭环，get的时候出现死循环(jdk8已经解决该问题)
 *
 *       原因：在transfer方法的while循环中, 线程A和线程B 操作了通一个链表e ，正是因为扩容之后链表中元素的会发生逆转, 所以会产生循环链表.
 *       jdk1.8中改进了resize方法，改进之后的方法不再进行链表的逆转, 而是保持原有链表的顺序, 如果在多线程环境下, 顶多会在链表后边多追加几个元素而已, 不会出现环的情况.

 *
 *    9.HashMap的Fail-Fast机制
 *    Entry<K,V> nextEntry() {
 *       if (modCount != expectedModCount)
 *       throw new ConcurrentModificationException();
 *                      ……
 *  }
 *   其中modCount为HashMap的一个实例变量，并且被声明为volatile，表示任何线程都可以看到该变量被其它线程修改的结果。
 *   （结构修改是指改变HashMap中的映射数或以其他方式修改其内部结构(例如，rehash)。此字段用于使HashMap的collection视图上的迭代器快速失败）
 *
 *   HashMap所采用的Fail-Fast机制本质上是一种乐观锁机制，通过检查状态——没有问题则忽略——有问题则抛出异常的方式，来避免线程同步的开销
 *
 *
 *
 *
 *   10.HashMap的遍历方案：
 *     从下面的测试代码中我们可以看到：HashMap的遍历方式有四种,主要的核心思路是：
 *
 *
 *       class KeyIterator extends HashIterator
 *         implements Iterator<K> {
 *         public final K next() { return nextNode().key; }
 *     }
 *
 *      class ValueIterator extends HashIterator
 *         implements Iterator<V> {
 *         public final V next() { return nextNode().value; }
 *     }
 *
 *      class EntryIterator extends HashIterator
 *         implements Iterator<Map.Entry<K,V>> {
 *         public final Map.Entry<K,V> next() { return nextNode(); }
 *     }
 *
 *
 *
 *
 *
 *
 *
 *
 */
public class HashMap_study {

    static final int MAXIMUM_CAPACITY = 1 << 30;

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }


    @Test
    public  void testSize(){

        int size=63;
        int i = tableSizeFor(size);
        System.out.println(i);

    }

    @Test
    public void testMaxSize(){
        HashMap<Integer,String>  map=new HashMap<>(Integer.MAX_VALUE);
        for(int i=0;i<Integer.MAX_VALUE;i++){

            map.put(i,"1");
            System.out.println(map.size());
        }
    }

    @Test
    public void test1(){
        Integer  integer=Integer.MAX_VALUE;
        System.out.println(integer);
        HashMap<String,Integer>  map=new HashMap<>(16);
        map.put("study1",100);
        map.put("study2",110);
        map.put("study3",120);
        System.out.println(map);
    }

    /**
     *   使用HashMap的匿名内部类Entry遍历比使用keySet()效率要高很多，使用forEach循环时要注意不要在循环的过程中改变键值对的任何一方的值，
     *   否则出现哈希表的值没有随着键值的改变而改变，到时候在删除的时候会出现问题。
     *
     *   此外，entrySet比keySet快些。对于keySet其实是遍历了2次，一次是转为iterator，一次就从hashmap中取出key所对于的value。而entrySet只是遍历了第一次，
     *   他把key和value都放到了entry中，所以就快了。
     */
    @Test
    public void test2(){
        HashMap<String,Integer>  map=new HashMap<>(16);
        map.put("study1",100);
        map.put("study2",110);
        map.put("study3",120);
        map.put("study4",120);
        map.put("study5",120);
        map.put("study6",120);




        //遍历方式一：entrySet()的 iterator迭代
        System.out.println("--------------entrySet()的 iterator迭代------------------");
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        Iterator<Map.Entry<String, Integer>> iterator = entries.iterator();
        while (iterator.hasNext()){
            Map.Entry<String, Integer> next = iterator.next();
            String key = next.getKey();
            Integer value = next.getValue();
            System.out.println(key+"="+value);
        }

        //遍历方式二：增强for循环
        System.out.println("--------------增强for循环------------------");
        for(Map.Entry<String,Integer>  entry:map.entrySet()){
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println(key+"="+value);
        }


        /**
         * 首先要获取键集合KeySet对象，然后再通过 KeySet 的迭代器KeyIterator进行遍历。KeyIterator 类继承自HashIterator类，核心逻辑也封装在 HashIterator 类中。
         * HashIterator 的逻辑并不复杂，在初始化时，(HashIterator 先从桶数组中找到包含链表节点引用的桶)。然后对这个桶指向的链表进行遍历。遍历完成后，
         * 再继续寻找下一个包含链表节点引用的桶，找到继续遍历。找不到，则结束遍历。举个例子，假设我们遍历下图的结构：
         */
        //用keySet遍历
        System.out.println("--------------keySet()的 iterator迭代------------------");
        Set<String> strings = map.keySet();
        Iterator<String> iterator1 = strings.iterator();
        while (iterator1.hasNext()){
            String key = iterator1.next();
            Integer value = map.get(key);
            System.out.println(key+"="+value);
        }

        //用Lambda表达式遍历
        System.out.println("--------------用Lambda表达式遍历------------------");
        map.forEach((k,v)-> System.out.println(k+"="+v));
    }
}
